#include <stdio.h>
#include "rbtree.h"
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
typedef struct data_s{
    struct rb_node rb;
    int data;
}DataNode;

////////////////////

static inline DataNode* rb_search_DataNode(struct rb_root *r,
						 int data)
{
	struct rb_node * n = r->rb_node;

    DataNode *tmp = 0;

	while (n)
	{
		tmp = rb_entry(n, DataNode, rb);

		if (data < tmp->data)
			n = n->rb_left;
		else if (data > tmp->data)
			n = n->rb_right;
		else
			return tmp;
	}
	return NULL;
}

static inline DataNode * __rb_insert(struct rb_root *r,
						   DataNode *n)
{
	struct rb_node ** p = &r->rb_node;
	struct rb_node * parent = NULL;
	DataNode *tmp = 0;

	while (*p)
	{
		parent = *p;
		tmp = rb_entry(parent, DataNode, rb);

		if(n->data < tmp->data)
			p = &(*p)->rb_left;
		else if (n->data > tmp->data)
			p = &(*p)->rb_right;
		else
			return tmp;
	}

	rb_link_node(&n->rb, parent, p);

	return NULL;
}

static inline DataNode * rb_insert(struct rb_root *r,
						 DataNode *n)
{
    DataNode *ret;
	DataNode *tmp = 0;
	if ((ret = __rb_insert(r, n)))
		goto out;
	rb_insert_color(&n->rb, r);
    printf("after insert data:%d\n", n->data);
 out:
	return ret;
}

///////////////////

DataNode *CreateDataNode(int data)
{
    DataNode *_new;
    _new = malloc(sizeof(DataNode));
    if (!_new) {
        return _new;
    } else {
    }
    _new->data = data;
    printf("data:%d\n", _new->data);
    return _new;
}

void show_func(struct rb_node *node)
{
    DataNode *tmp = NULL;
    if (node) {
        tmp = rb_entry(node, DataNode, rb);
        printf("%d\t", tmp->data);
    }
}

int main(int argc, const char *argv[])
{
    int i = 0, j;
    struct rb_root *m_root = malloc(sizeof(struct rb_root));
    DataNode *tmp = 0;
    DataNode **pNodes = NULL;
    int nodesize = 0;
    struct rb_node *tmp_ = 0;
    if (!m_root)
        return -1;

    scanf("%d", &j);
    nodesize = j;
    pNodes = (DataNode**)malloc(sizeof(DataNode*)*nodesize);
    memset(pNodes, 0, nodesize);
        srand((unsigned)time(NULL));
    //  insert data node
    while (j) {
        i = rand()%100;
        tmp = CreateDataNode(i);
        if (tmp) {
            tmp = rb_insert(m_root, tmp);
            j--;
        }
        if (tmp)
            j--;
    }
#if 0
    tmp_ = m_root->rb_node;
    while (tmp_) {
        tmp = rb_entry(tmp_, DataNode, rb);
        if (tmp) { 
        //    printf("address:%x\n", tmp);
        //    printf("data:%d\n", tmp->data);
        }
        tmp_ = rb_next(tmp_);
//        printf("");
    }
#endif
#if 0
    scanf("%d", &j);
    tmp = rb_search_DataNode(m_root, j);
    if (tmp)
        printf("make it\n");
    else 
        printf("it is null\n");

    printf("oh yesh!\n");
#endif

    //  cengxubianli
    int curNodeNumber = 0;
    int curCengN = 1;
    int curNodeN = pow(2, curCengN-1);
    DataNode *curCengNode;
    while (curNodeNumber < nodesize) {
        curNodeN = pow(2, curCengN-1);
        if (curNodeNumber == 0) {
            pNodes[curNodeNumber] = rb_entry(m_root->rb_node, DataNode, rb);
        } else {
            for (int i = 0, j = pow(2, curCengN-2); i < curNodeNumber, 0 < j; j--) {
                pNodes[curNodeNumber + i] = rb_entry(pNodes[curNodeNumber - j]->rb.rb_left, DataNode, rb);   
                i++;
                pNodes[curNodeNumber + i] = rb_entry(pNodes[curNodeNumber - j]->rb.rb_right, DataNode, rb);   
                i++;
            }
        }

        curCengN++;
        curNodeNumber += curNodeN;
    }
    curNodeNumber = pow(2,0);
    for (int i = 0, j = 1; i < nodesize; i++) {
        if (curNodeNumber == i) {
            curNodeNumber += pow(2, j);
            j++;
            printf("\n");
        }
        if (pNodes[i]) {
            printf("%d  ", pNodes[i]->data);
        } else {
            printf("nil  ");
        }
    }
    int n;
    printf("\n");
    n = rb_get_size(m_root);
    printf("the size of tree:%d\n", n);
    printf("\n");
    printf("preorder:\n");
    rb_preorder_show(m_root->rb_node, show_func);
    printf("\n");
    printf("infixorder:\n");
    rb_infixorder_show(m_root->rb_node, show_func);
    printf("\n");
    printf("postorder:\n");
    rb_postorder_show(m_root->rb_node, show_func);
    printf("\n");

    int size = 0;
    struct rb_node **rb_nodes = (struct rb_node**)malloc(sizeof(struct rb_node*)*nodesize*10);
    rb_preorder_get(m_root->rb_node, rb_nodes, &size);
    printf("get size:%d\n", size);
    printf("get everyone:\n");
    for (int i = 0; i < size; i ++) {
        tmp = rb_entry(rb_nodes[i], DataNode, rb);
        printf("%d\n", tmp->data);
    }

    return 0;
}
